This invention pertains generally to the field of semiconductor non-volatile data storage system architectures and their methods of operation and, more specifically, to the management of data structures in such memories.
A common application of flash EEPROM devices is as a mass data storage subsystem for electronic devices. Such subsystems are commonly implemented as either removable memory cards that can be inserted into multiple host systems or as non-removable embedded storage within the host system. In both implementations, the subsystem includes one or more flash devices and often a subsystem controller.
Flash EEPROM devices are composed of one or more arrays of transistor cells, each cell capable of non-volatile storage of one or more bits of data. Thus flash memory does not require power to retain the data programmed therein. Once programmed however, a cell must be erased before it can be reprogrammed with a new data value. These arrays of cells are partitioned into groups to provide for efficient implementation of read, program and erase functions. A typical flash memory architecture for mass storage arranges large groups of cells into erasable blocks, wherein a block contains the smallest number of cells (unit of erase) that are erasable at one time.
In one commercial form, each block contains enough cells to store one sector of user data plus some overhead data related to the user data and/or to the block in which it is stored. The amount of user data included in a sector is the standard 512 bytes in one class of such memory systems but can be of some other size. Because the isolation of individual blocks of cells from one another that is required to make them individually erasable takes space on the integrated circuit chip, another class of flash memories makes the blocks significantly larger so there is less space required for such isolation. But since it is also desired to handle user data in much smaller sectors, each large block is often further partitioned into individually addressable pages that are the basic unit for reading and programming user data. Each page usually stores one sector of user data, but a page may store a partial sector or multiple sectors. A “sector” is used herein to refer to an amount of user data that is transferred to and from the host as a unit.
The subsystem controller in a large block system performs a number of functions including the translation between logical addresses received by the memory sub-system from a host, and physical addresses within the memory cell array. This translation often involves use of intermediate terms for a logical block number (LBN) and logical page. The controller also manages the low-level flash circuit operation through a series of commands that it issues to the flash memory devices via an interface bus. Another function the controller performs is to maintain the integrity of data stored to the subsystem through various means, such as by using an error correction code (ECC).
Data from the host is typically just provided to the memory system identified as logical sectors. For example, the host will send data described in terms of a starting logical sector and the total number of sectors. Within the host, these logical sectors may be structured into larger units, but this information is typically not passed on to the memory's controller. (Knowledge of these host structures can be used, though, to have physical structures in the memory or controller constructs reflect these host structures as they will reflect how the host transfers data: for example, memories are typically structured to store user data based on a physical sector that is the same size as a logical sector.) The controller organizes the host structures into logical constructs that mimic the physical structure for more efficient storage of them in the physical memory. For example, in a common arrangement the memory system controller groups logical sectors (as defined by the host) into logical blocks that correspond in size to the physical structure of a block, which is the physical unit of erase for a flash type memory. The controller can then maintain the relation of the physical structures to the logical constructs, for instance in the form of a Sector Address Table (SAT), and updated this correspondence as the logical to physical relation changes.
For greater efficiency, memory systems often increase parallelism by introducing larger structures. For instance, in memory system having a number of semi-autonomous arrays that can be written, read, or both, concurrently, blocks from different arrays are grouped into “meta-block” structures and the controller will form logical blocks of data into corresponding logical meta-blocks, allowing for the multiple blocks to be operated upon at the same time. This arrangement is beneficial for sequential read and writes of logically contiguous sectors of relatively large amounts of data. It has a number of negative effects, though, when there is need to manipulate data of a finer granularity as the system must work with the larger structures. For example, if the host repeatedly reads and writes a single logical sector, the entire meta-block will be repeatedly read and written due only the single “hot” sector, resulting in all of the overhead and time latencies from the large data structures being deposited upon this single sector. Consequently, flash and other memory system would benefit greatly from techniques that allow them to use large data structures, and the resultant efficiency gained from increased parallelism, for large amounts of logically contiguous sectors of data, while also allowing smaller data structures to be readily accessed.